Geometric computations are wide-spread and, in fact, essential in many real-world problems. One problem experienced by systems that represent objects as geometric shapes is that the objects may become so complex and the computational effort required to manipulate them so unmanageable (in terms of time and/or memory), that their use becomes intractable. One tactic to deal with this problem is to decompose objects into simpler components such as, for example, convex objects (convex objects are often preferred because many algorithms work more efficiently on convex objects). Convex decomposition (approximate and exact, may be used for a number of applications: collision detection (in two- or three-dimensional systems); mesh generation (for modeling physically based deformations); motion planning (e.g., to generate and control an object's motion through an environment); pattern recognition (for a physics-based approach to motion estimation); point location (determining if a point is inside or outside a polygon or polyhedra); shape representation (representing a complex shape by a collection of simpler convex shapes); and skeletonization (extracting features from images/polygons to represent the shape of objects, used for creating realistic character animations).
By way of example only, one use of convex decomposition operations is in the development of two-dimensional (2D) graphics for computer-based games. To assist game developers (and others who wish to use 2D graphics) software development kits (SDKs) have been modified over time to permit the use of 2D graphics engines to support full animation. Referring to FIG. 1, prior art 2D graphics system 100 operates on objects 105 from graphics frame 110. Initially, graphics engine 115 performs whatever operations on objects 105 the program developer has specified such as, for example, their rotation and/or translation. Physics engine 120 may be applied to one or more objects 105 to simulate, for example, friction, gravity, collisions between objects and fluid dynamics. (It will be recognized that in many graphics systems such as 2D graphics system 100, the objects operated on by physics engine 120 must be specifically designated.) Once both graphics engine 115 and physics engine 120 have executed, render engine 125 is applied to generate updated scene 130. Updated scene 130, in turn, may represent an animated sequence of graphics frames in accordance with output from physics engine 120.
One reason convex decompositions are not used more extensively is that they are often not practical for complex models. For example, an exact convex decomposition (ECD) can be costly to construct and result in a representation with an unmanageable number of elements. And, while a minimum set of convex components may be efficiently computed for simple polygons without holes, the problem is NP-hard for polygons with holes. An alternative to ECD is to partition or decompose a given shape into approximately convex pieces. For many applications, the approximately convex components produced by approximate convex decomposition (ACD) strategies provide similar benefits as ECD, while generated shapes are both significantly smaller and more efficiently computed.